#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<array>

using namespace std;

struct Element
{
	int key;
	char data[30];
};

class CountingSort
{
public:
	CountingSort(Element * elearray, int sizen)
	{
		dataarray = elearray;
		size = sizen;
		sortedarray = new Element[size];
	}//end constructor

	Element * sortarray()
	{
		int maxkey = dataarray[0].key;
		for (int index = 0; index < size; index++)
		{
			if (dataarray[index].key > maxkey)
				maxkey = dataarray[index].key;
		}//end loop

		int * temparray = new int[maxkey];
		for (int index = 0; index < maxkey; index++)
			temparray[index] = 0;

		//C[i] now contains number of elements equal to i.
		for (int index = 0; index < size; index++)
			temparray[dataarray[index].key - 1] ++;

		for (int index = 1; index < maxkey; index++)
			temparray[index] += temparray[index - 1];

		for (int index = size - 1; index >= 0; index--)
		{
			sortedarray[temparray[dataarray[index].key - 1] - 1] = dataarray[index];
			//printf("Data is %d\n", temparray[dataarray[index].key - 1]);
			temparray[dataarray[index].key - 1]--;
		}//end loop

		return sortedarray;
	}//end function: Sorting

	~CountingSort()
	{
		printf("Sorting finishes!\n");
		system("pause");
	}//end distructor

private:
	int size;
	Element * dataarray;
	Element * sortedarray;
};//end class